import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/4 14:57
 * @description 贪心 + 双指针，维护字典序最大和次大的字符下标
 */
public class Solution {
    public static void main(String[] args) {

    }
    public String repeatLimitedString(String s, int repeatLimit) {
        int[] cnt = new int[26];
        StringBuilder sb = new StringBuilder();
        // 字典序最大的字母下标
        int r = 0;
        for (char ch: s.toCharArray()) {
            cnt[ch - 'a']++;
            r = Math.max(r, ch - 'a');
        }
        // 字典序次大的字母下标
        int l = r - 1;
        while (r >= 0) {
            // 尝试更新 l
            while (l >= 0 && cnt[l] == 0) {
                --l;
            }
            // 不超过 repeatLimit的字典序最大字符
            int rep = Math.min(cnt[r], repeatLimit);
            for (int i = 0 ; i < rep; i++) {
                sb.append((char) ('a' + r));
            }
            // 用了之后减少
            cnt[r] -= rep;
            if (cnt[r] == 0) {
                // 字典序最大的用完了，那么次大的变成最大
                r = l;
                l = r - 1;
            }else if (l < 0) {
                break;
            }else {
                // 添加一个字典序次大的字符，然后继续添加字典序最大的字符
                sb.append((char) ('a' + l));
                --cnt[l];
            }
        }
        return sb.toString();
    }
}
